package 栈和队列;

import java.util.*;

public class MaxSlidingWindow {
    //暴力O(n^2)过不了
//    public int[] maxSlidingWindow(int[] nums, int k) {
//        //Deque<Integer> deque = new ArrayDeque<>();
//        int[] result = new int[nums.length-k+1];
//        int m = 0;
//        for(int i=0;i<nums.length-k+1;i++){
//            int max = -999999;
//            for(int j=i;j<i+k;j++){
//                System.out.println(nums[j]);
//                if(nums[j]>max){
//                    max = nums[j];
//                }
//            }
//            result[m++] = max;
//        }
//        return result;
//    }
//    public int[] maxSlidingWindow(int[] nums, int k) {
//        Deque<Integer> deque = new ArrayDeque<>();
//        Deque<Integer> deque1 = new ArrayDeque<>();
//        int[] result = new int[nums.length-k+1];
//        int m = 0;
//        for(int i=0;i<nums.length;i++){
//            if(i<3){
//                deque.add(nums[i]);
//                if(i==0 || nums[i]>deque1.peek())   deque1.addFirst(nums[i]);
//                continue;
//            }
//            if(i==3) result[m++] = deque1.peek();
//        }
//        return result;
//    }
    //方法一：优先队列
//    public int[] maxSlidingWindow(int[] nums, int k) {
//        int n = nums.length;
//        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
//            @Override
//            public int compare(int[] o1, int[] o2) {
//                return o1[0]!=o2[0]?o2[0]-o1[0]:o2[1]-o1[1];//从大到小排序
//            }
//        });
//        for(int i=0;i<k;i++){
//            queue.offer(new int[]{nums[i],i});    //先取第一个滑动窗口，将第一个滑动窗口入队列
//        }
//        int[] ans = new int[n-k+1]; //存放结果
//        ans[0] = queue.peek()[0];   //第一个滑动窗口的最大值
//        for(int i=k;i<n;i++){
//            queue.offer(new int[]{nums[i],i });
//            while(queue.peek()[1]<i-k+1){
//                queue.poll();   //找到滑动窗口内的最大值
//            }
//            ans[i-k+1] = queue.peek()[0];
//        }
//        return ans;
//    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        int[] ans = new int[n-k+1];
        ans[0] = nums[deque.peekFirst()];
        for(int i=k;i<n;i++){
            while(!deque.isEmpty()&&nums[i]>=nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst()<i-k+1){
                deque.pollFirst();
            }
            ans[i-k+1] = nums[deque.peekFirst()];
        }
        return ans;
    }
    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int n = nums.length;
            int[] prefixMax = new int[n];
            int[] suffixMax = new int[n];
            for (int i = 0; i < n; ++i) {
                if (i % k == 0) {
                    prefixMax[i] = nums[i];
                }
                else {
                    prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
                }
            }
            for (int i = n - 1; i >= 0; --i) {
                if (i == n - 1 || (i + 1) % k == 0) {
                    suffixMax[i] = nums[i];
                } else {
                    suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
                }
            }

            int[] ans = new int[n - k + 1];
            for (int i = 0; i <= n - k; ++i) {
                ans[i] = Math.max(suffixMax[i], prefixMax[i + k - 1]);
            }
            return ans;
        }
    }

}
